package com.mystudy.leetcode.problem.tree.p_1008;

import com.mystudy.leetcode.base.TreeNode;

/**
 * @program: infoalgorithm
 * @description: 先序遍历构造二叉树
 * @author: zhouzhilong
 * @create: 2019-07-26 16:32
 **/
public class Solution {

    /**
     * 对于二叉搜索树来说，其先序遍历可以唯一确定一颗二叉搜索树
     * @param preorder
     * @return
     */
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = null;
        for (int i = 0; i < preorder.length; i++) {
            root = add(root,preorder[i]);
        }
        return root;
    }

    private TreeNode add(TreeNode node,int value){
        if(node == null){
            return new TreeNode(value);
        }
        if(value<node.val){
            node.left = add(node.left,value);
        }
        if(value>node.val){
            node.right = add(node.right,value);
        }
        return node;
    }

}
